Any modern digital map (or mathematical graph, as they are sometimes known) of a road or other navigable network, in its simplest form, is effectively a database containing data representative of nodes, most commonly representative of road intersections, and lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length, but are more commonly separate. Nodes may be considered “real” or “valid” for the purposes of this application when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas “artificial” or “avoidable” nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road or a means of identifying the position along a road at which some characteristic of that road changes, e.g. a speed limit.
In practically all modern digital maps, nodes and segments are further defined by various attributes which are again represented by data in the database, e.g. each node will typically have geographical coordinates to define its real-world position, e.g. latitude and longitude. The complete “graph” of the road network is described by millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.
In the context of devising a means of efficiently referencing or describing a line location (i.e. a path through a road network), it is not only highly inefficient simply to provide an ordered list of all nodes (and/or segments, and optionally their attributes) within the digital map which form part of the location, but such a referencing method would necessitate that exactly the same digital map was used during any de-referencing which later occurred, for example in a mobile device to which the location reference was transmitted, because nodes, segments, lines and their attributes are practically only ever uniquely defined in a particular version of a map created by a particular map vendor. Even fundamental attributes such as longitude and latitude for a particular node might differ between different digital maps.
One particular attribute often provided in digital maps is a Traffic Message Channel (TMC) location table reference. TMC is a technology for delivering traffic and travel information to vehicle users, and more particularly to navigation systems (either portable or integrated) present within those vehicles and which include some form of digital map. A TMC message consists of an event code (which need not be traffic-specific, although these are most common) and a location code, often consisting of an ordered list of location references by means of which the location of the traffic event can be determined in the digital map and thus represented graphically on the screen of the navigation system. A number of pre-defined nodes in most commercially available digital maps are assigned a TMC location reference which is determined with reference to a limited location table.
Although TMC messages are very efficient in that they can be as short as 37 bits in length and therefore do not impinge significantly on available bandwidth for broadcast data, only a fixed number of location references are available, and therefore typically only motorways and major highways (or intersections thereon) in each country offering TMC can be referenced.
In order to overcome the deficiencies in pre-coded location referencing methods, e.g. TMC, a number of dynamic location referencing methods have been developed in recent years. Typically, these dynamic location referencing methods encode a location, e.g. a line location, by referencing nodes within a first digital map by their geographic coordinates, together with certain attributes of segments therebetween. This information can then be decoded or resolved on a second, different digital map to determine the equivalent location within the second digital map.
One example of a dynamic location referencing method is known as AGORA-C. A complete description of the AGORA-C location referencing approach can be found in the ISO Standard 17572-3 Intelligent Transport System (ITS)—Location Referencing for Geographic Databases—Part 3: Dynamic Location References, but the fundamentals of the approach are that a location reference can be completely specified by a set of location points, specified by coordinate pairs of latitude and longitude and ordered in a list, each point complying with various rules but most importantly being consecutive in terms of the location being referenced and the previous point in the list, i.e. successive points form a next-point-relationship. As with other location referencing systems, each point is provided with a number of attributes which assist in better defining that point, but specific to the AGORA-C method is the identification of each point as one of a Location Point (LP), an Intersection Point (IP), or a Routing Point (RP). LPs mark the start and end positions of the referenced location. Each point along the location at which the road section signature changes is represented by an IP, so locations being paths over a road network and which pass through intersections without any road section signature change need not be referenced by an intersection point. Routing points are provided where an intersection points alone are insufficient to unambiguously determine the correct location in the decoder, and are either added as separate points, or where a required routing point coincides with existing intersection point, a simple attribute change on the latter is made.
Another dynamic location referencing method is OpenLR™, which is an open source software project launched by TomTom International B.V. in September 2009 to provide an open standard for encoding, transmitting and decoding location references in digital maps. A complete description of the OpenLR™ location referencing approach can be found in the material provided at www.openlr.org, such as the OpenLR™ White Paper (latest version being v1.5 published on 17 Jan. 2012). Further details about the manner in which a line location is encoded can be found in the patent publication WO 2010/000707, and the manner by which it is decoded in the patent publication WO 2010/000706; the entire content of both documents being incorporated herein by reference. The main idea behind OpenLR™ is to describe a line location along the navigable network represented by a digital map by a concatenation of one or more, typically a plurality of, shortest paths. Each shortest path is specified by information about its start line and its end line. This information is combined in so-called location reference points (LRPs). The LRPs are ordered from the start of the location to the end of the location and the shortest-path between two subsequent LRPs covers a part of the location. The concatenation of all these shortest-paths covers the location completely and this path is called the location reference path. The location reference path may be longer than the original location and offsets trim this path down to the size of the location path. Thus, for each line location, at least two LRPs are needed for the start and end of the location, with intermediate LRPs acting as a guide for the route calculation. Attributes taken from the digital map are also associated with all LRPs, except the last LRP in the ordered list, in the encoded location reference. These attributes, which include the bearing (e.g. the angle between the true North and a line which is defined by the coordinate of the LRP and a coordinate which is a predetermined distance along the line defined by the LRP attributes), functional road class (i.e. a road classification based on the importance of the road), and form of way (i.e. the physical road type, e.g. motorway, multiple lane carriageway, single lane carriageway) define the outgoing path from each LRP forming the location reference path.
A number of other alternate dynamic location referencing methods are also in existence, such as TPEG-ULR. Again, however, an encoded line location reference according to TPEG-ULR comprises an ordered list of two or more locations defined by their geographical coordinates, together with additional information, such as direction, category (e.g. street category) and height, for use in resolving the encoded line location.
One common type of location that it is encoded using such dynamic location referring methods is a point location along a line. Such a point location is not simply described using its geographical coordinates, but in addition by its relation to a segment of the road or navigable network. More specifically, the location is typically defined as being a certain distance, commonly referred to as an offset, along the line between at least two nodes, and can be further defined as being on either side of the line, on both sides of the line, or directly on the line, and even in some embodiments as having an orientation with respect to the driving direction along the line. Examples of such locations can be: house numbers; address points; and points of interest (POIs), such as petrol stations, shopping malls, restaurants, indication loops and even speed cameras.
Although dynamic location referencing methods are typically highly accurate and offer a very high chance of a decoded location being equal to the original location that was encoded, e.g. more than 90%, there will some locations that can't be successfully decoded. In such situations, i.e. when an encoded location fails to be resolved, that location is essentially lost and a device using the digital map (on which the locations are being decoded) will not be able to display or otherwise use the location. Thus, for example, when the locations being decoded relate to speed cameras or other speed enforcement devices, this can lead to a user not being notified of a camera, despite it being known to exist.
The present invention aims to provide a method of mitigating this experience by ensuring that an approximate position can always be determined for any received encoded “point along a line” location even if the regular decoding process fails.